package com.yang.Offer;

public class Offer33 {
}

class Offer33Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 后序遍历是左右中  那么有 右>中>左 0 1 2
        // 第一个大于根节点的肯定是右子树的,因为右子树的都比根节点和左子树大  所以 可以划分范围
        // 1.划分左右子树[i,j]  j为根节点(后序遍历) 找到的第一个大于根节点的数是 m  有范围左子树[i, m-1], 右子树[m ,j-1] j根节点
        // 2.判断是否为二叉搜索树 而左子树都小于根节点 所以 刚开始进行划分的时候已经确定了 左子树肯定都为正确的 只需要判断右子树即可
        // 一样 只需要判断右子树范围内的数 都大于根节点，遇到小于的跳出 右子树范围到根节点都无处则返回true
        // 通过指针完成所有的操作
        return recur(postorder, 0, postorder.length - 1);
    }
    private boolean recur(int[] postorder, int i, int j){
        // 空子树 必然只能对了
        if(i >= j){
            return true;
        }
        // 保留左子树起始点
        int p = i;
        // 找到第一个大于根节点的值
        while(postorder[p] < postorder[j]){
            p ++;
        }
        // 保存左右子树分界点
        int m = p;
        // 再判断是否右子树都大于根节点
        while(postorder[p] > postorder[j]){
            p ++;
        }
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}
